package uestc.lj.advanced.dp;

import java.util.LinkedList;

/**
 * @Author:Crazlee
 * @Date:2021/12/10
 */
public class Code03_ExpressionCompute {

	public static int expressionCompute(String str) {
		return process(str.toCharArray(), 0)[0];
	}

	/**
	 * 从str[i...]往后计算，遇到字符串终止位置或者右括号停止，返回两个值
	 *
	 * @param str 表达式
	 * @param i   当前计算到的位置
	 * @return 1. 从i开始到结束位置或者右括号位置的计算结果。2. 遇到的结束位置
	 */
	private static int[] process(char[] str, int i) {
		LinkedList<String> stack = new LinkedList<>();
		int num = 0;
		int[] result = null;

		while (i < str.length && str[i] != ')') {
			if (str[i] > '0' && str[i] < '9') {
				num = num * 10 + str[i] - '0';
				i++;
			} else if (str[i] != '(') {
				// 遇到运算符号
				addNum(stack, num);
				stack.addLast(String.valueOf(str[i++]));
			} else {
				// 遇到左括号了
				result = process(str, i + 1);
				num = result[0];
				i = result[1] + 1;
			}
		}
		addNum(stack, num);
		return new int[]{getNum(stack), i};
	}

	/**
	 * 计算栈中表达式的值
	 *
	 * @param stack 栈
	 * @return 表达式的值
	 */
	private static int getNum(LinkedList<String> stack) {
		int result = 0;
		boolean add = true;
		String cur = null;
		int num = 0;
		while (!stack.isEmpty()) {
			cur = stack.pollFirst();
			if ("+".equals(cur)) {
				add = true;
			} else if ("-".equals(cur)) {
				add = false;
			} else {
				num = Integer.parseInt(cur);
				result += add ? num : -num;
			}
		}
		return result;
	}

	/**
	 * 将num压入栈中，但是要注意乘除的优先级和加减的优先级
	 *
	 * @param stack 栈
	 * @param num   数
	 */
	private static void addNum(LinkedList<String> stack, int num) {
		if (!stack.isEmpty()) {
			int cur = 0;
			String top = stack.pollLast();

			if ("+".equals(top) || "-".equals(top)) {
				stack.addLast(top);
			} else {
				cur = Integer.parseInt(stack.pollLast());
				num = "*".equals(top) ? cur * num : cur / num;
			}
		}
		stack.addLast(String.valueOf(num));
	}
}
